home *** CD-ROM | disk | FTP | other *** search
/ Chip 1996 April / CHIP 1996 aprilis (CD06).zip / CHIP_CD06.ISO / hypertxt.arj / 9509 / CHIKEDD.CD < prev    next >
Text File  |  1996-03-10  |  10KB  |  157 lines
  1.           @VRejtvénymegfejtés@N
  2.  
  3.           @VTéglalapok és különbségek@N
  4.  
  5.               Az alábbiakban  a májusi  és júniusi  CHIP-ben megjelent
  6.           feladványok megfejtéseit tesszük közzé.
  7.               Téglalap-szabászat címmel  jelent meg  májusi számunkban
  8.           szokásos fejtörônk, melyre -- eddig példa nélkül álló  módon
  9.           --  nem  érkeztek   megfejtések.  Az  alábbiakban   ezért  a
  10.           megoldások ismertetése, értékelése helyett röviden  vázoljuk
  11.           a feladat  egy lehetséges  megoldási útját,  mintegy ötletet
  12.           adva az elinduláshoz.
  13.               Kirakósdi  címû  rejtvényünk röviden  a  következô volt:
  14.           több   kisebb-nagyobb   téglalapból   kell   összerakni  egy
  15.           nagyobbat, úgy hogy a kisebb téglalapok oldalául csak  @K1@N-tôl
  16.           @KN@N-ig használhatjuk fel  a természetes mindegyikét,  pontosan
  17.           egyszer. Keressük  tehát azokat  az @KN@N  számokat, melyekre  a
  18.           feladat  megoldható,   természetesen  a   kisebb  téglalapok
  19.           oldalaival együtt.
  20.               A legkisebb szám, melyre megoldás található (a triviális
  21.           @KN=2@N-höz tartozó  @K1*2@N-es télalapon  kívül), az  @KN=10@N, azaz öt
  22.           darab  kis  téglalapból  rakható  össze  egy  nagyobb  --  a
  23.           mellékelt  ábrán  a  sok  lehetséges  elrendezés  közül  egy
  24.           látható (1. ábra).
  25.  
  26.           @<9509\tegla2.gif>■■@N  1. ábra
  27.  
  28.               Hogyan tudunk egy ilyen elrendezést összehozni, kirakni?
  29.           Egy lehetséges, távolról sem optimális, meglehetôsen  favágó
  30.           jellegû eljárás  lehet a  következô. Ållítsuk  elô sorba egy
  31.           adott @KN@N  szám esetén  az összes  lehetséges (@KN/2@N hosszúságú)
  32.           számpár-sorozatot.  (Ezek  száma  @KN@N-nel  rohamosan  nô,   az
  33.           @K1*3*5*..*(n/2-1)@N  összefüggés  szerint.)  Egy pár-sorozathoz
  34.           (ilyen például az ábráról  leolvasható 1*2, 3*9, 4*8,  5*10,
  35.           6*7) készítsük el a területösszeget (ez esetünkben 153).  Ha
  36.           ez  prímszám,  akkor  már léphetünk  is  tovább  a következô
  37.           pársorozatra,  hiszen  ekkor  nem  lehetséges  egy   nagyobb
  38.           téglalap kirakása. Ha összetett szám a területösszeg,  akkor
  39.           állítsuk   elô   annak   valódi   két-tényezôs  felbontásait
  40.           (példánkban  3*51  és  9*17).  Ezek  meghatároznak   egy-egy
  41.           keret-téglalapot,    melyeket    ezek    után   megpróbálunk
  42.           szisztematikusan  feltölteni az  aktuális pár-sorozat  által
  43.           reprezentált    téglalapokkal    visszalépéses   (backtrack)
  44.           algoritmus szerint.  Itt ügyelnünk  kell az  @KX-Y@N koordináták
  45.           lehetséges cseréire, az elforgatásokra. Amenyiben sikerült a
  46.           keretet feltöltenünk,  akkor megoldást  találtunk, ellenkezô
  47.           esetben vennünk kell az  újabb keretet (felbontást). Ha  egy
  48.           terület-összeg minden lehetséges felbontását kimerítve sincs
  49.           megoldás, elô  kell vennünk  az újabb  pár-sorozatot, és így
  50.           tovább.   A   programot  némileg   gyorsabbá   tehetjük,  ha
  51.           figyelembe vesszük, hogy a kis téglalapok (mint az ábrán  is
  52.           látható) egyfajta spirális rendben töltik ki a nagyot.
  53.               A  feladat  érdekes továbbgondolása  az  a kérdés,  hogy
  54.           lehetséges-e csupa különbözô négyzetbôl téglalapot,  illetve
  55.           négyzetet  összeállítani.  Elôször  1925-ben  sikerült   egy
  56.           lengyel  matematikusnak  kilenc  különbözô  négyzetbôl   egy
  57.           téglalapot  összevarázsolnia.  Négyzetet  elôször   1939-ben
  58.           rakott össze egy német matematikus, méghozzá 55 darab kisebb
  59.           négyzetbôl, de ez a szám egy éven belül 28-ra csökkent,  két
  60.           angol matematikus (igen komoly apparátust használó)  munkája
  61.           révén. ïk (Stone és Tutte) mellesleg azt is bebizonyították,
  62.           hogy kilencnél  kevesebb különbözô  négyzetbôl téglalap  nem
  63.           rakható ki, tehát 1925-ben Moron rögtön a minimumot  találta
  64.           meg. 1948-ban tovább csökkent a nagy négyzet  elôállításához
  65.           szükséges  négyzetek  száma, Willcokcksnak  sikerült  ezt az
  66.           értéket  24-re  levinnie.  Harminc  évnek  kellett  eltelnie
  67.           ahhoz, hogy -- immár számítástechnikai eszközöket  használva
  68.           --  Duijvestijn  holland matematikus  bebizonyítsa,  hogy 21
  69.           különbözô  négyzetbôl   kirakható  egy   nagy  négyzet,   de
  70.           kevesebbet  használva  nem.  Hogy  meglehetôs  számú  esetet
  71.           kellett végigvizsgálnia, arra utal a korábbi eredmény,  mely
  72.           szerint a legfeljebb  15 négyzetbôl összerakható  téglalapok
  73.           száma 3683. Ha Olvasóink  esetleg kedvet kapnának az  önálló
  74.           kísérletezésre  a  négyzetekkel,  és  ez  netán  nem vezetne
  75.           eredményre, a ""21-es"  megoldás elrendezését megtalálják  a
  76.           KöMaL (Középiskolai Matematikai Lapok) 1980/7. számában.
  77.  
  78.  
  79.           @VSikertelen különbségek@N
  80.  
  81.               Júniusi számunkban a Különbözô különbségek címû rejtvény
  82.           jelent  meg,  melyre  -- talán  a  nyári  kánikula, talán  a
  83.           szünidô, a szabadság, de lehet, hogy maga a feladat miatt --
  84.           csak a határidô után érkezett megfejtés, Földvári  Csongoré.
  85.           îgy  az   Olvasóink  megoldásainak   bemutatása,  értékelése
  86.           helyett itt egy lehetséges megoldási utat vázolunk.
  87.               A feladat szövege szerint minél több @KN@N-re keressük meg a
  88.           legkisebb ""felsô" számmal rendelkezô szám ""@KN@N-est",  melyre
  89.           a páronként képzett  különbségek mind különböznek  -- @KN=4@N-re
  90.           ilyen például a @K0, 1, 4, 6@N számnégyes. (A látszólag  öncélú,
  91.           elvont     feladat     komoly     jelentôséggel     bír    a
  92.           rádiócsillagászatban,  vagy  röntgen-krisztallográfiában, az
  93.           érdeklôdôk  errôl  részletesebben  olvashatnak  a   Tudomány
  94.           1986/2. számában, A. K. Dewdney cikkében.)
  95.               Ha a  rejtvény szövegében  közölt példát  megvizsgáljuk,
  96.           látható, hogy nemcsak különböznek a páronkénti  különbségek,
  97.           de elôállítják az 1  és 6 közötti összes  természetes számot
  98.           is (ezt könnyû ellenôrizni egy szám-gráf megrajzolásával  --
  99.           mint az ábrán is látható). Azt is könnyen beláthatjuk,  hogy
  100.           ilyen ""tökéletes"  szám @KN@N-es  csak három  van --  ezek mind
  101.           megtalálhatók az ábrán.
  102.  
  103.           @<9509\szakasz.gif>■■@N  2. ábra
  104.  
  105.               Tehát  ezek után  keresni csak  olyan @KN@N-eseket  érdemes,
  106.           ahol a különbségek ugyan  különböznek, de nem merítik  ki az
  107.           összes  természetes  számot,  azaz  nem  tökéletesek.  Ilyen
  108.           például @KN=5@N-re @K11@N-es minimális felsô határral a @K0, 1, 4,  9,
  109.           @K11@N  számötös,  melynek   tagjait  minden  lehetséges   módon
  110.           párosítva a következô különbségek adódnak: @K1, 2, 3, 4, 5, 7,
  111.           8,  9, 10,  11@N --  azaz tényleg  különbözôek, és  csak  a  6
  112.           hiányzik.  Érdekes,  hogy   @KN=6@N-ra  két  darab,   lényegesen
  113.           különbözô,  azonos   minimális  felsô   határral  rendelkezô
  114.           számsorozat is adódik: a @K0, 1, 4,  10, 12, 17 és a 0, 1,  8,
  115.           11, 13, 17.@N Kérdés lehet, hogy más @KN@N-re is található-e  több
  116.           (azonos  legkisebb   felsô  határral   rendelkezô)  sorozat,
  117.           természetesen a ""tükrözéssel" megkaphatókat nem  figyelembe
  118.           véve?
  119.               Hogyan kereshetôk  meg ezek  a sorozatok?  Algoritmusunk
  120.           megint távol  áll az  optimálistól --  de a  kezdeti lépések
  121.           megtételére alkalmas. A problémát kissé átfogalmazzuk: az  @KN@N
  122.           darab szám helyett @KN-1@N darab szakaszt (intervallumot) fogunk
  123.           keresni, melyeket ha egymás után pakolunk, akkor a  keresett
  124.           számokat  fogjuk  megkapni.  Induljunk  ki  az  @K1@N hosszúságú
  125.           szakaszból, s vegyünk mellé egy nála nála hosszabb szakaszt.
  126.           Ekkor már van  három számunk @K(0,  1, K)@N, most  ellenôriznünk
  127.           kell, hogy a különbségek mind különböznek-e. Ha igen,  jöhet
  128.           egy  újabb  (ismét  eltérô  hosszúságú)  szakasz,  s   újabb
  129.           ellenôrzése  a  különbségeknek.  Ezeket  a  lépéseket  addig
  130.           folytatjuk, amíg meg nincs az  @KN-1@N darab szakasz (azaz az  @KN@N
  131.           szám). Most már csak a felsô határ minimalizálása van  hátra
  132.           --   ezt   megtehetjük   úgy,   hogy   az   egész  programot
  133.           visszalépésesen írjuk meg, s  ha az összhossz nem  kisebb az
  134.           eddigi maximumnál (elsô esetben egy alkalmasan megválasztott
  135.           számnál),  akkor   valahonnan  újra   kezdjük  a   szakaszok
  136.           elôállítását.
  137.  
  138.           @KBánhegyesi Zoltán@N
  139.  
  140.  
  141.           @Vùj rejtvényünk@N
  142.  
  143.           @VLiftezzünk!@N
  144.  
  145.               A feladatot  rögtön általánosan  fogalmazzuk meg:  adott
  146.           egy @KN@N szintes  épület egyetlen lifttel,  amelybe @KK@N utas  fér
  147.           egyszerre. A lift két szint közötti utat pontosan  egységnyi
  148.           idô alatt teszi meg. Az @KI@N-edik szinten kezdetben @KC(I)@N  számú
  149.           utas tartózkodik, s az épületben tartózkodók közül  pontosan
  150.           @KD(J)@N számúan akarnak a  @KJ@N-edik szintre utazni. A  feladatunk
  151.           az, hogy a lehetô  legrövidebb idô alatt mindenkit  a kívánt
  152.           helyre utaztassunk programunk segítségével.
  153.  
  154.               Beküldési határidô: 1995. szeptember 30.
  155.  
  156.           @KB.Z.@N
  157.